home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 2000 November: Tool Chest / Dev.CD Nov 00 TC Disk 1.toast / Sample Code / Contributed / SpriteWorld / SpriteWorld Files / Utils / SWCompressResource.c < prev    next >
Encoding:
C/C++ Source or Header  |  2000-10-06  |  10.2 KB  |  462 lines  |  [TEXT/CWIE]
  1. #ifndef __MEMORY__
  2. #include <Memory.h>
  3. #endif
  4.  
  5. #include <SWCompressResource.h>
  6.  
  7. /**************************************************************
  8.     LZSS.C -- A Data Compression Program
  9.     (tab = 4 spaces)
  10. ***************************************************************
  11.     4/6/1989 Haruhiko Okumura
  12.     Use, distribute, and modify this program freely.
  13.     Please send me your improved versions.
  14.         PC-VAN        SCIENCE
  15.         NIFTY-Serve    PAF01022
  16.         CompuServe    74050,1022
  17. **************************************************************/
  18.  
  19. //    Modified by Anders F Björklund <afb@algonet.se>
  20.  
  21. #define N                     4096    /* size of ring buffer, power of two */
  22. #define F                       18        /* upper limit for match_length */
  23. #define THRESHOLD            2       /* encode string into position and length
  24.                                        if match_length is greater than this */
  25.  
  26. #define NIL                    N        /* index for root of binary search trees */
  27.  
  28. #define OFTEN_CHARACTER     0x00    /* any character that will appear often */
  29.  
  30. #define EOF                    -1
  31.  
  32. #define kSignature            'LZSS'
  33. #define kHeaderSize            (sizeof(long) + sizeof(long))
  34.  
  35.  
  36. static unsigned char        *text_buf;    /* ring buffer of size N,
  37.                                        with an extra F-1 bytes to facilitate string comparison */ 
  38.  
  39. static unsigned char        *in,*out;
  40. static long                    in_len,out_len;
  41.  
  42. #define GET_CHAR(ch)        ((ch = (--in_len < 0) ? EOF: *in++ ) != EOF)
  43. #define PUT_CHAR(ch)        out_len++, *out++ = ch
  44.  
  45. static unsigned long int    textsize = 0,            /* text size counter */
  46.                             codesize = 0;            /* code size counter */
  47.  
  48. static int                    match_position, match_length; 
  49.                             /* of longest match.  These are set by the InsertNode() procedure. */
  50. static int                    *lson, *rson, *dad; 
  51.                             /* left & right children & parents -- These constitute binary search trees. */
  52.  
  53.  
  54. static void InitTree(void);
  55. static void InsertNode(int r);
  56. static void DeleteNode(int p);
  57.  
  58. static void Encode(void);
  59. static void Decode(void);
  60.  
  61. /* --------------------------------------------------------------------------------------------------- */
  62.  
  63. OSErr EnterCompression(void)
  64. {
  65.     text_buf = (unsigned char *) NewPtr( N + F - 1);
  66.  
  67.     if ( text_buf == NULL)
  68.         return memFullErr;
  69.     
  70.     lson = (int *) NewPtr( sizeof(int) * ( N + 1 ) );
  71.     rson = (int *) NewPtr( sizeof(int) * ( N + 1 + 256 ) );
  72.     dad = (int *) NewPtr( sizeof(int) * ( N + 1 ) );
  73.  
  74.     if ( lson == NULL || rson == NULL || dad == NULL )
  75.         return memFullErr;
  76.         
  77.     return noErr;
  78. }
  79.  
  80. void  ExitCompression(void)
  81. {
  82.     if ( text_buf)
  83.         DisposePtr((Ptr)text_buf);
  84.     if ( lson)
  85.         DisposePtr((Ptr)lson);
  86.     if ( rson)
  87.         DisposePtr((Ptr)rson);
  88.     if ( dad)
  89.         DisposePtr((Ptr)dad);
  90.  
  91. }
  92.  
  93. OSErr CompressHandle( Handle source, Handle *dest )
  94. {
  95.     Handle    srcHdl,dstHdl;
  96.     Ptr        srcPtr,dstPtr;
  97.     Size    srcLen,dstLen;
  98.     long    *longP;
  99.     OSErr    err;
  100.  
  101.     srcHdl = source;
  102.     *dest = NULL;
  103.         
  104.     if ( text_buf == NULL )
  105.     {
  106.         err = EnterCompression();
  107.         if ( err != noErr )
  108.             return err;
  109.     }
  110.             
  111.     srcLen = GetHandleSize( srcHdl );
  112.     dstHdl = NewHandle( 2 * srcLen + kHeaderSize);
  113.     if ( dstHdl == NULL )
  114.         return memFullErr;
  115.         
  116.     srcPtr = *srcHdl;
  117.     dstPtr = *dstHdl + kHeaderSize;
  118.     
  119.     in = (UInt8*)srcPtr;    out = (UInt8*)dstPtr;
  120.     in_len = srcLen;        out_len = 0;    
  121.     Encode();
  122.     dstLen = out_len;
  123.  
  124.     longP = (long *) (*dstHdl);
  125.     longP[0] = kSignature;
  126.     longP[1] = srcLen;
  127.  
  128.     SetHandleSize( dstHdl, dstLen + kHeaderSize);
  129.     
  130.     *dest = dstHdl;
  131.     return noErr;
  132. }
  133.  
  134.  
  135. OSErr DecompressHandle( Handle source, Handle *dest )
  136. {
  137.     Handle    srcHdl,dstHdl;
  138.     Ptr        srcPtr,dstPtr;
  139.     Size    srcLen,dstLen;
  140.     long    *longP;
  141.     OSErr    err;
  142.     
  143.     srcHdl = source;
  144.     *dest = NULL;
  145.  
  146.     if ( text_buf == NULL )
  147.     {
  148.         err = EnterCompression();
  149.         if ( err != noErr )
  150.             return err;
  151.     }
  152.     
  153.     srcLen = GetHandleSize(srcHdl) - kHeaderSize;
  154.     longP = (long *) *srcHdl;
  155.     if ( srcLen <= 0 || longP[0] != kSignature)
  156.         return paramErr;
  157.     dstLen = longP[1];
  158.  
  159.     dstHdl = NewHandle( dstLen );
  160.     if ( dstHdl == NULL )
  161.         return memFullErr;
  162.  
  163.     srcPtr = *srcHdl + kHeaderSize;
  164.     dstPtr = *dstHdl;
  165.     
  166.     in = (UInt8*)srcPtr;    out = (UInt8*)dstPtr;
  167.     in_len = srcLen;        out_len = 0;
  168.     Decode();
  169.     
  170.     *dest = dstHdl;
  171.     return noErr;
  172. }
  173.  
  174. Boolean IsHandleCompressed( Handle source )
  175. {
  176.     Size    srcLen;
  177.     long    *longP;
  178.     
  179.     srcLen = GetHandleSize(source) - kHeaderSize;
  180.     longP = (long *) *source;
  181.  
  182.     if ( srcLen <= 0 || longP[0] != kSignature)
  183.         return false;
  184.     else
  185.         return true;
  186. }
  187.  
  188. #pragma mark -
  189.  
  190. void InitTree(void)  /* initialize trees */
  191. {
  192.     int  i;
  193.  
  194.     /* For i = 0 to N - 1, rson[i] and lson[i] will be the right and
  195.        left children of node i.  These nodes need not be initialized.
  196.        Also, dad[i] is the parent of node i.  These are initialized to
  197.        NIL (= N), which stands for 'not used.'
  198.        For i = 0 to 255, rson[N + i + 1] is the root of the tree
  199.        for strings that begin with character i.  These are initialized
  200.        to NIL.  Note there are 256 trees. */
  201.  
  202.     for (i = N + 1; i <= N + 256; i++)
  203.         rson[i] = NIL;
  204.     
  205.     for (i = 0; i < N; i++)
  206.         dad[i] = NIL;
  207.  
  208. }
  209.  
  210. void InsertNode(int r)
  211.     /* Inserts string of length F, text_buf[r..r+F-1], into one of the
  212.        trees (text_buf[r]'th tree) and returns the longest-match position
  213.        and length via the global variables match_position and match_length. 
  214.  
  215.        If match_length = F, then removes the old node in favor of the new
  216.        one, because the old one will be deleted sooner.
  217.        Note r plays double role, as tree node and position in buffer. */
  218. {
  219.     int  i, p, cmp;
  220.     unsigned char  *key;
  221.  
  222.     cmp = 1;
  223.     key = &text_buf[r];
  224.     p = N + 1 + key[0];
  225.  
  226.     rson[r] = lson[r] = NIL;
  227.     match_length = 0;
  228.     for ( ; ; ) {
  229.         if (cmp >= 0) {
  230.             if (rson[p] != NIL)
  231.                 p = rson[p];
  232.             else {
  233.                 rson[p] = r;
  234.                 dad[r] = p;
  235.                 return;
  236.             }
  237.         }
  238.         else {
  239.             if (lson[p] != NIL)
  240.                 p = lson[p];
  241.             else {
  242.                 lson[p] = r;
  243.                 dad[r] = p;
  244.                 return;
  245.             }
  246.         }
  247.         for (i = 1; i < F; i++)
  248.             if ((cmp = key[i] - text_buf[p + i]) != 0)
  249.                 break;
  250.         if (i > match_length) {
  251.             match_position = p;
  252.             if ((match_length = i) >= F)
  253.                 break;
  254.         }
  255.     }
  256.     dad[r] = dad[p];
  257.     lson[r] = lson[p];
  258.     rson[r] = rson[p];
  259.  
  260.     dad[lson[p]] = r;
  261.     dad[rson[p]] = r;
  262.     if (rson[dad[p]] == p)
  263.         rson[dad[p]] = r;
  264.     else
  265.         lson[dad[p]] = r;
  266.     dad[p] = NIL;  /* remove p */
  267. }
  268.  
  269. void DeleteNode(int p)  /* deletes node p from tree */
  270. {
  271.     int  q;
  272.  
  273.     if (dad[p] == NIL)
  274.         return;  /* not in tree */
  275.     if (rson[p] == NIL)
  276.         q = lson[p];
  277.     else if (lson[p] == NIL)
  278.         q = rson[p];
  279.     else {
  280.         q = lson[p];
  281.         if (rson[q] != NIL) {
  282.             do {
  283.                 q = rson[q];
  284.             } while (rson[q] != NIL);
  285.             rson[dad[q]] = lson[q];
  286.             dad[lson[q]] = dad[q];
  287.             lson[q] = lson[p];
  288.             dad[lson[p]] = q;
  289.         }
  290.         rson[q] = rson[p];
  291.         dad[rson[p]] = q;
  292.     }
  293.     dad[q] = dad[p];
  294.     if (rson[dad[p]] == p)
  295.         rson[dad[p]] = q;
  296.     else
  297.         lson[dad[p]] = q;
  298.  
  299.     dad[p] = NIL;
  300. }
  301.  
  302. #pragma mark -
  303.  
  304. void Encode(void)
  305. {
  306.     int  i, c, len, r, s, last_match_length, code_buf_ptr;
  307.     unsigned char  code_buf[17], mask;
  308.  
  309.     InitTree();  /* initialize trees */
  310.  
  311.     code_buf[0] = 0;
  312.         
  313.     /*  code_buf[1..16] saves eight units of code, and
  314.         code_buf[0] works as eight flags, "1" representing that the unit
  315.         is an unencoded letter (1 byte), "0" a position-and-length pair 
  316.  
  317.         (2 bytes).  Thus, eight units require at most 16 bytes of code.  
  318. */
  319.  
  320.     code_buf_ptr = mask = 1;
  321.     s = 0;
  322.     r = N - F;
  323.  
  324.     for (i = s; i < r; i++)
  325.     {
  326.         text_buf[i] = OFTEN_CHARACTER;  /* Clear the buffer with
  327.         any character that will appear often. */
  328.     }
  329.         
  330.     for (len = 0; (len < F) && GET_CHAR(c); len++ )
  331.     {
  332.         text_buf[r + len] = c;  /* Read F bytes into the last F bytes of the buffer */
  333.     }
  334.     
  335.     if ((textsize = len) == 0)
  336.         return;  /* text of size zero */
  337.     
  338.     for (i = 1; i <= F; i++)
  339.         InsertNode(r - i);  /* Insert the F strings,
  340.         each of which begins with one or more 'space' characters.  Note 
  341.  
  342.         the order in which these strings are inserted.  This way,
  343.         degenerate trees will be less likely to occur. */
  344.     InsertNode(r);  /* Finally, insert the whole string just read.  The
  345.         global variables match_length and match_position are set. */
  346.     do {
  347.         if (match_length > len)
  348.             match_length = len;  /* match_length
  349.             may be spuriously long near the end of text. */
  350.         if (match_length <= THRESHOLD) {
  351.             match_length = 1;  /* Not long enough match.  Send one byte. */
  352.             code_buf[0] |= mask;  /* 'send one byte' flag */
  353.             code_buf[code_buf_ptr++] = text_buf[r];  /* Send uncoded. */
  354.         } else {
  355.             code_buf[code_buf_ptr++] = (unsigned char) match_position;
  356.             code_buf[code_buf_ptr++] = (unsigned char)
  357.                 (((match_position >> 4) & 0xf0)
  358.                 | (match_length - (THRESHOLD + 1)));  /* Send position and
  359.                     length pair. Note match_length > THRESHOLD. */
  360.         }
  361.         if ((mask <<= 1) == 0) {  /* Shift mask left one bit. */
  362.             for (i = 0; i < code_buf_ptr; i++)  /* Send at most 8 units of */
  363.             {
  364.                 PUT_CHAR(code_buf[i]);     /* code together */
  365.             }
  366.             
  367.             codesize += code_buf_ptr;
  368.             code_buf[0] = 0;  code_buf_ptr = mask = 1;
  369.         }
  370.         last_match_length = match_length;
  371.         
  372.         for (i = 0; i < last_match_length && GET_CHAR(c); i++ )
  373.         {
  374.             DeleteNode(s);        /* Delete old strings and */
  375.             text_buf[s] = c;    /* read new bytes */
  376.             if (s < F - 1) text_buf[s + N] = c;  /* If the position is
  377.                 near the end of buffer, extend the buffer to make
  378.                 string comparison easier. */
  379.             s = (s + 1) & (N - 1);
  380.             r = (r + 1) & (N - 1);
  381.                 /* Since this is a ring buffer, increment the position
  382.                      modulo N. */
  383.             InsertNode(r);    /* Register the string in text_buf[r..r+F-1] */
  384.         }
  385.     
  386.         while (i++ < last_match_length) {    /* After the end of text, */
  387.             DeleteNode(s);                    /* no need to read, but */
  388.             s = (s + 1) & (N - 1);
  389.             r = (r + 1) & (N - 1);
  390.             if (--len) InsertNode(r);        /* buffer may not be empty. */
  391.         }
  392.     } while (len > 0);    /* until length of string to be processed is zero */
  393.  
  394.     if (code_buf_ptr > 1) {        /* Send remaining code. */
  395.         for (i = 0; i < code_buf_ptr; i++)
  396.         {
  397.             PUT_CHAR(code_buf[i]);
  398.         }
  399.         codesize += code_buf_ptr;
  400.     }
  401. }
  402.  
  403. void Decode(void)    /* Just the reverse of Encode(). */
  404. {
  405.     int  i, j, k, r, c;
  406.     unsigned int  flags;
  407.  
  408.     r = N - F;
  409.     flags = 0;
  410.  
  411.         /* Clear the buffer with any character that will appear often. */
  412.     for (i = 0; i < r; i++)
  413.     {
  414.         text_buf[i] = OFTEN_CHARACTER;
  415.     }
  416.         
  417.     for ( ; ; )
  418.     {
  419.         flags >>= 1;
  420.         if ((flags & 256) == 0)
  421.         {
  422.             if ( !GET_CHAR(c) )
  423.                 break;
  424.         
  425.             flags = c | 0xff00;        /* uses higher byte cleverly, to count eight*/
  426.         }    
  427.         
  428.         if (flags & 1)
  429.         {
  430.             if ( !GET_CHAR(c) )
  431.                 break;
  432.             
  433.             PUT_CHAR(c);
  434.             
  435.             text_buf[r++] = c;
  436.             r &= (N - 1);
  437.         }
  438.         else
  439.         {
  440.             if ( !GET_CHAR(i) )
  441.                 break;
  442.         
  443.             if ( !GET_CHAR(j) )
  444.                 break;
  445.         
  446.             i |= (j & 0xf0) << 4;
  447.             j = (j & 0x0f) + THRESHOLD;
  448.  
  449.             for (k = 0; k <= j; k++)
  450.             {
  451.                 c = text_buf[(i + k) & (N - 1)];
  452.                 
  453.                 PUT_CHAR(c);
  454.                 
  455.                 text_buf[r++] = c;
  456.                 r &= (N - 1);
  457.             }
  458.         }
  459.     }
  460. }
  461.  
  462.